<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $len = count($nums);
        $left = 0;
        $right = $len - 1;
        if ($len == 0)
            return -1;
        if ($len == 1)
            return $nums[0] == $target ? 0 : -1;
        while ($left <= $right){
            $mid = $left + (($right - $left)>>1);
            if ($nums[$mid] == $target)
                return $mid;
            if ($nums[$left] <= $nums[$mid]){
                if ($nums[$left] <= $target && $target < $nums[$mid]){
                    $right = $mid - 1;
                } else {
                    $left = $mid + 1;
                }
            } else {
                if ($nums[$mid] < $target && $target <= $nums[$len - 1] ){
                    $left =  $mid + 1;
                } else {
                    $right = $mid - 1;
                }
            }
        }
        return -1;
    }
}
